package algorithm.node;

import java.util.*;

class Solution {

      public class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }

    public ListNode detectCycle(ListNode head) {
          //0或1个不成环，为false
          if(head== null || head.next ==null) return null;
          ListNode pFast = head, pSlow = head;
          while (pFast !=null && pFast.next!=null){
                  pSlow = pSlow.next;
                  pFast = pFast.next.next;
              if (pFast == pSlow ){
                  // 快慢指针相遇，此时从head 和 相遇点处，同时查找直至相遇
                  ListNode p3 = head;
                  while (p3 !=pSlow){
                      p3 = p3.next;
                      pSlow = pSlow.next;

                  }
                  return p3; // 返回环的入口
              }
          }
          return null;//没环就遍历到null了，也不相遇
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          //题目中节点数目可能为0
        if(headA == null || headB ==null) return null;
        ListNode p1 = headA, p2 = headB;

          while (p1 != p2){
        //要么是 p1.next 要么是 headB，两者是互斥的。
              p1 = p1 !=null? p1.next : headB;
              p2 = p2 !=null? p2.next : headA;
          }
          //如果两个不等的话，都指向为空， return null;
          //如果两个等的话，都指向同一个节点, return
        return p1;
    }



    public ListNode removeNthFromEnd(ListNode head, int n) {
          //n可能删除的是头结点。所以虚拟结点来处理。
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode p1 = dummyNode, p2 = dummyNode;
        for (int i = 0; i < n; i++) {
            p1 = p1.next; //先遍历n个
        }
        while (p1.next !=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        p2.next = p2.next.next;
        return dummyNode.next;
    }



    public ListNode swapPairs(ListNode head) {
          if (head == null || head.next == null) {
              return head;
          }
          ListNode dummyHead = new ListNode(-1);
          dummyHead.next = head;//将虚拟头结点指向head
          ListNode cur = dummyHead;
          ListNode firstNode,secondNode,threeNode;
          //短路与，第一个成立才判断第二个。
          while (cur.next != null && cur.next.next != null){
              firstNode = cur.next;  // 临时节点，保存两个节点之中的第一个节点
              secondNode = cur.next.next; // 临时节点，保存两个节点之中的第2个节点
              threeNode = cur.next.next.next;  // 临时节点，保存两个节点之中的第3个节点

              cur.next = secondNode; //指向改变1
              secondNode.next = firstNode; //指向改变2
              firstNode.next = threeNode;    //指向改变3
              //改变循环变量, 准备下一轮交换
              cur = firstNode ; // cur移动 (firstNode是移动完成后的第2个，此时它前面的元素都已经完成交换)
          }
          return dummyHead.next;
    }












    public ListNode reverseList(ListNode head) {
        //按双指针思路搞：递归写法就是替代了双指针法的初始化这步。
        //ListNode cur = head;
        //ListNode pre = null;
        return reverse(null, head);//初始翻转

    }
    public ListNode reverse(ListNode pre, ListNode cur){//反转操作
        if(cur==null){return pre;}
        ListNode temp = cur.next;
        cur.next = pre;//翻转1次
        //和双指针法对比，递归的写法，其实就是做了这两步
        //pre = cur;// 更新pre 和 cur指针
        //cur = temp;//前进
        return reverse(cur, temp);//翻转
    }


public ListNode reverseList1(ListNode head) {
      ListNode cur = head, temp = head;
      ListNode pre = null;
      while(cur!=null){ //cur=null的时候，pre = head
        temp = cur.next;// 保存cur的下一个节点，因为接下来要改变cur
        cur.next = pre;//反转1次
        pre = cur;// 更新pre 和 cur指针
        cur = temp;//前进
    }
    return pre;
}

//删除结点的步骤：找到该结点的前一个结点，进行删除操作。
//    添加一个虚拟头结点，删除头结点就不用另做考虑
public ListNode removeElements(ListNode head, int val) {

      if (head == null){
          return head;
      }
      ListNode dummy = new ListNode(-1);
      dummy.next = head;
      ListNode cur = dummy;
      while (cur.next !=null){
          //判断 cur.next 的元素是否为 val ；是的话就操作，cur.next 变成了新的 ，指针不用往后移动
          // 就需要判断 这个新的结点 cur.next 是否为 val
          if (cur.next.val == val){
              cur.next = cur.next.next;
          }else {
              cur = cur.next;
          }

      }
      return dummy.next;
}
}


